package com.yuqingsong.algorithm.sort;

import java.util.Arrays;
import java.util.Comparator;

public class QuickSort<T> extends AbstractSort<T>{

	public QuickSort(Comparator<? super T> comp) {
		init(comp);
	}

	
	@Override
	public T[] sort(T[] array) {
		quicksort(array, 0, array.length-1);
		return array;
	}

	private void quicksort(T[] array,int p, int r) {
		if (p < r) {
			int q = partition(array,p, r);
			quicksort(array,p, q - 1);
			quicksort(array,q + 1, r);
		}
	}

	public int partition(T[] array,int p, int r) {
		T x = array[r];
		int less = p - 1;
		for (int i = p; i < r; i++) {
			if (comp.compare(array[i], x) <= 0) {
				less++;
				swap(array,less, i);
			}
		}
		less++;
		swap(array,less, r);
		return less;
	}


	public static void main(String[] args) {
		Integer[] temp = null;
		temp = new Integer[] { 16, 14, 8, 7, 9, 3, 2, 4, 1 };

		Comparator<Integer> comp = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		};
		Sort<Integer> sort = new QuickSort<Integer>( comp);
		Integer[] clone = temp.clone();
		Arrays.sort(clone);
		boolean equals = Arrays.equals(clone, sort.sort(temp));
		assert equals;
		System.out.println(Arrays.toString(temp));
	}


	
}
